package com.itheima.leetcode.od.b.dynamicprogramming;

import java.util.ArrayList;
import java.util.HashSet;

/**
 * (A卷,100分)- 称砝码（Java & JS & Python）
 * <p>
 * 题目描述
 * <p>
 * 现有n种砝码，重量互不相等，分别为 m1,m2,m3…mn ；
 * <p>
 * 每种砝码对应的数量为 x1,x2,x3...xn 。现在要用这些砝码去称物体的重量(放在同一侧)，问能称出多少种不同的重量。
 * <p>
 * 输入描述
 * <p>
 * 对于每组测试数据：
 * <p>
 * 第一行：n --- 砝码的种数(范围[1,10])
 * <p>
 * 第二行：m1 m2 m3 ... mn --- 每种砝码的重量(范围[1,2000])
 * <p>
 * 第三行：x1 x2 x3 .... xn --- 每种砝码对应的数量(范围[1,10])
 * <p>
 * 输出描述
 * <p>
 * 利用给定的砝码可以称出的不同的重量数
 * <p>
 * 备注
 * 数据范围：每组输入数据满足：
 * <p>
 * 1 ≤ n ≤ 10
 * <p>
 * 1 ≤ mi ≤ 2000
 * <p>
 * 1 ≤ xi ≤ 10
 * <p>
 * 用例
 * <p>
 * 输入	2
 * <p>
 * 1 2
 * <p>
 * 2 1
 * <p>
 * 输出	5
 * <p>
 * 说明	可以表示出0，1，2，3，4五种重量。
 * <p>
 * 题目解析
 * <p>
 * 本题可以使用多重背包求解。关于多重背包问题，其实就是01背包的变种问题。
 * <p>
 * 01背包问题：
 * <p>
 * 有N种物品，每种物品只有一个，第 i 个物品的重量为 wi，价值为pi，另外还有一个承重为W的背包，问该背包在不超载的情况下，装入物品的最大价值是多少?
 * <p>
 * 多重背包问题
 * <p>
 * 有N种物品，第 i 个物品的重量为 wi，价值为pi，数量为ci，另外还有一个承重为W的背包，问该背包在不超载的情况下，装入物品的最大价值是多少?
 * <p>
 * 想求解多重背包问题，需要先弄得01背包问题，最好也了解下01背包的滚动数组优化：
 * <p>
 * 算法设计 - 01背包问题_01背包算法_伏城之外的博客-CSDN博客
 * <p>
 * 算法设计 - 01背包问题的状态转移方程优化，以及完全背包问题_01背包问题状态转移方程_伏城之外的博客-CSDN博客
 * <p>
 * 学会01背包后，多重背包问题的求解就非常简单了，其实我们可以将多重背包问题，转化为01背包问题，怎么转化呢？
 * <p>
 * 举个例子：你有红富士苹果10个，那么是不是等价于红富士苹果A有1个，红富士苹果B有1个，...，红富士苹果J有1个？
 * <p>
 * 其实这就是多重背包转化为01背包的方法。即将1种物品N个，转化为N种物品1个。
 * <p>
 * 关于多重背包的求解有两种解法：
 * <p>
 * 1、朴素解法
 * <p>
 * 2、二进制优化解法
 * <p>
 * 这两种解法具体逻辑请看：华为校招机试 - 攻城战（Java & JS & Python）_伏城之外的博客-CSDN博客
 * <p>
 * 本题中
 * <p>
 * N种砝码  →  N种物品
 * <p>
 * 每种砝码的重量  → 每种物品的重量
 * <p>
 * 每种砝码的重量  → 每种物品的价值
 * <p>
 * 每种砝码的数量  → 每种物品的数量
 * <p>
 * 所有砝码的重量之和  → 背包承重
 * <p>
 * 本题要求的是：用给的砝码能组合出多少种重量
 * <p>
 * 而这其实刚好和求解背包问题时，遍历所有可能的背包承重相符，因此本题非常适合当成背包问题求解。
 */
public class WeighingWeight {
    public static void main(String[] args) {
        /*Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        int[] m = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            m[i] = sc.nextInt();
        }

        int[] x = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            x[i] = sc.nextInt();
        }*/

        int[] m = new int[3];
        m[1] = 1;
        m[2] = 2;
        int[] x = new int[3];
        x[1] = 2;
        x[2] = 1;
        System.out.println(getResult(2, m, x));
    }

    /**
     * 完全背包
     *
     * @param n
     * @param m
     * @param x
     * @return
     */
    public static int getResult(int n, int[] m, int[] x) {
        int bag = 0;
        for (int i = 1; i <= n; i++) {
            bag += m[i] * x[i];
        }

        boolean[] dp = new boolean[bag + 1];
        dp[0] = true;

        for (int i = 1; i <= n; i++) {
            for (int j = bag; j >= m[i]; j--) {
                for (int k = 1; k <= x[i]; k++) {
                    if (j >= m[i] * k) { // 起始
                        if (dp[j - m[i] * k]) {
                            dp[j] = true;
                        }
                    }
                }
            }
        }

        int count = 0;
        for (boolean flag : dp) {
            if (flag) {
                count++;
            }
        }

        return count;
    }

    /**
     * 暴力枚举
     *
     * @param n
     * @param w
     * @param nums
     */
    public static void getResult2(int n, int[] w, int[] nums) {
        HashSet<Integer> set = new HashSet<>();
        set.add(0);
        for (int i = 0; i < n; i++) {
            ArrayList<Integer> current_res = new ArrayList<>(set);
            for (int j = 1; j <= nums[i]; j++) {
                for (int k = 0; k < current_res.size(); k++) {
                    set.add(current_res.get(k) + w[i] * j);
                }
            }
        }
        System.out.println(set.size());
    }
}